/**
 * 给出n数对。在每一个数对中，第一个数字总是比第二个数字小。
 *
 * 现在，我们定义一种跟随关系，当且仅当b < c时，数对(c, d)才可以跟在(a, b)后面。我们用这种形式来构造一个数对链。
 *
 * 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
 *
 *
 *思路：贪心+二分
 * https://leetcode.cn/problems/maximum-length-of-pair-chain/
 */
class FindLongestChainBinary {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs,(o1,o2)->o1[0]-o2[0]);
        int len=pairs.length;
        List<Integer> arr=new ArrayList<>();
       for(int[] p:pairs) {
           int x=p[0];
           int y=p[1];
           if(arr.isEmpty()||x>arr.get(arr.size()-1)) {
               arr.add(y);
           } else{
            int idx = binarySearch(arr, x);
            arr.set(idx, Math.min(arr.get(idx), y));
           }
       }
       return arr.size();
    }
    public int binarySearch(List<Integer> arr,int y) {
        int low=0;
        int high=arr.size()-1;
        while(low<high) {
            int mid=low+((high-low)>>>1);
            if(arr.get(mid)>=y) {
                high=mid;
            }else {
               low=mid+1; 
            }
            
        }
        return low;
    }
}